package com.atguigui.leetcode;

/**
 * 878.第 N 个神奇数字
 * Project: leetcode
 * Package: com.atguigui.leetcode
 * Version: 1.0
 * <p>
 * Created by WJX on 2022/11/22 9:22
 */
public class P878NthMagicalNumber {

    public static void main(String[] args) {
        Solution solution = new P878NthMagicalNumber().new Solution();

        System.out.println(solution.nthMagicalNumber(25, 4, 6));

        // TO TEST
    }

    class Solution {
        private static final long MOD = (long) 1e9 + 7;

        public int nthMagicalNumber(int n, int a, int b) {
            long lcm = a / gcd(a, b) * b;
            long left = 0, right = (long) Math.max(a, b) * n; // 开区间 (left, right)
            while (left + 1 < right) { // 开区间不为空
                //二分
                long mid = left + (right - left) / 2;
                //mid / a == 多少个被a整除
                //mid / b == 多少个被b整除
                //mid / lcm == 重复统计的
                if (mid / a + mid / b - mid / lcm >= n)
                    right = mid; // 范围缩小到 (left, mid)
                else
                    left = mid; // 范围缩小到 (mid, right)
            }
            return (int) (right % MOD);
        }

        /**
         * 最小公因数
         *
         * @param a
         * @param b
         * @return a和b的最小公因数
         */
        private int gcd(int a, int b) {
            return b == 0 ? a : gcd(b, a % b);
        }
    }
}
